package BinaryTree;
// 94-中序遍历二叉树-easy

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class InorderTraversal {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static List<Integer> inorderDfs(TreeNode root){
        if(root == null) return null;
        dfs(root);
        return res;
    }
    private static List<Integer> res = new ArrayList<>();
    private static void dfs(TreeNode root){
        // 递归终止条件
        if(root == null) return;
        dfs(root.left);
        res.add(root.val);
        dfs(root.right);
    }
    public static List<Integer> inorderRecur(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                ans.add(root.val);
                root = root.right;
            }
        }
        return ans;
    }
    public static TreeNode buildTree(String[] nodes){
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int index = 1;
        while(index < nodes.length && !queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.left);
            }
            index++;
            if(index < nodes.length && !nodes[index].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(",");
        TreeNode root = buildTree(nodes);
        System.out.println(inorderDfs(root));
        System.out.println(inorderRecur(root));
        sc.close();
    }
}
